#include<stdio.h>
#include<malloc.h>

typedef struct joseph_ring
{
    int number;
    struct joseph_ring *next;
}person;

person * init(int n){
    person *head=(person *)malloc(sizeof(person));
    head->number=1;
    head->next=NULL;
    person *circle=head;
    for(int i=2;i<=n;i++){
        person *temp=(person *)malloc(sizeof(person));
        temp->number=i;
        temp->next=NULL;
        circle->next=temp;
        circle=circle->next;
    }
    circle->next=head;
    return head;
}

void findAndKill(person *head, int k, int m){
    person *tail=head;
    // 找到链表第一个节点的上一个节点，为删除操作做准备
    while(tail->next!=head){
        tail=tail->next;
    }
    person *p=head;
    // 找到编号为k的人
    while(p->number!=k){
        tail=p;
        p=p->next;
    }
    // 从编号为k的人开始，只有符合p->next==p时，说明链表中除了p节点，所有编号都出列了
    while(p->next!=p){
        //找到从p报数1开始，报m的人，并且还要知道数m-1de人的位置tail，方便做删除操作。
        for(int i=1;i<m;i++){
            tail=p;
            p=p->next;
        }
        //从链表上将p结点摘下来
        tail->next=p->next;
        printf("出列人的编号为:%d\n",p->number);
        free(p);
        //继续使用p指针指向出列编号的下一个编号，游戏继续
        p=tail->next;
    }
}

int main(){
    printf("输入圆桌上的人数n:");
    int n;
    scanf("%d", &n);
    person *head = init(n);
    printf("从第k人开始报数(k>1且k<%d)：",n);
    int k;
    scanf("%d",&k);
    printf("数到m的人出列：");
    int m;
    scanf("%d",&m);
    findAndKill(head, k, m);
    return 0;
}